package main

import (
	"fmt"
)

/**
 * @param source: A string
 * @param target: A string
 * @return: A string denote the minimum window, return "" if there is no such a string
 */
func MinWindow(source string, target string) string {
	smap := map[byte]int{}
	tmap := map[byte]int{}

	for i := -0; i < len(target); i++ {
		c := byte(target[i])
		_, ok := tmap[c]
		if !ok {
			tmap[c] = 0
		}
		tmap[c] += 1
	}

	minwin := 2147483647
	ans := ""
	n := len(source)
	right := 0
	matched := 0
	for left := 0; left < n; left++ {
		for right < n && matched < len(tmap) {
			ch := byte(source[right])

			_, ok := smap[ch]
			if !ok {
				smap[ch] = 0
			}
			smap[ch] += 1

			_, ok1 := tmap[ch]
			if ok1 && smap[ch] == tmap[ch] {
				matched++
			}

			right++
		}

		if matched == len(tmap) {
			if right-left < minwin {
				minwin = right - left
				ans = source[left:right]
			}
		}

		ch := byte(source[left])
		smap[ch] -= 1

		_, ok3 := tmap[ch]

		if ok3 && smap[ch] == tmap[ch]-1 {
			matched--
		}
	}
	return ans
}

func main() {
	fmt.Println(MinWindow("abc", "ac"))
	fmt.Println(MinWindow("adobecodebanc", "abc"))
	fmt.Println(MinWindow("abc", "aa"))
	fmt.Println(MinWindow("abcdecf", "acc"))
}
